package com.leetcode.LeetCode精选TOP面试题;

/**
 * @author 覃国强
 * @date 2022-05-23 17:32
 */
public class 题库_0044_通配符匹配 {

  public static void main(String[] args) {
    String s = "abcabczzzde";
    String p = "*abc???de*";

    Solution solution = new Solution();
    boolean match = solution.isMatch(s, p);

    System.out.println(match);
  }

  static
  class Solution {
    public boolean isMatch(String s, String p) {
//      return isMatchWithDp(s, p);
      if (s == null) {
        return p == null;
      }
      if (s.length() == 0) {
        if (p == null) {
          return false;
        }
        for (char ch : p.toCharArray()) {
          if (ch != '*') {
            return false;
          }
        }
        return true;
      }
      return isMatch(s, 0, p, 0);
    }

    private boolean isMatchWithDp(String s, String p) {

      int m = p.length() + 1;
      int n = s.length() + 1;
      boolean[][] dp = new boolean[m][n];
      dp[0][0] = true;
      for (int i = 1; i < m && p.charAt(i - 1) == '*'; ++i) {
        dp[i][0] = true;
      }

      for (int i = 1; i < m; ++i) {
        for (int j = 1; j < n; ++j) {
          if (p.charAt(i - 1) == '*') {
            dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
          } else if (p.charAt(i - 1) == '?' || p.charAt(i - 1) == s.charAt(j - 1)) {
            dp[i][j] = dp[i - 1][j - 1];
          }
        }
      }

      return dp[p.length()][s.length()];
    }

    private boolean isMatch(String s, int i, String p, int j) {
      if (i == s.length()) {
        for (; j < p.length(); ++j) {
          if (p.charAt(j) != '*') {
            return false;
          }
        }
        return true;
      }
      if (j == p.length()) {
        return false;
      }

      char pCh = p.charAt(j);
      if (pCh == '*') {
        // j 向后寻找第一个非 * 的字符
        while (j < p.length() && p.charAt(j) == '*') {
          ++j;
        }
        if (j == p.length()) {
          return true;
        }
        // i 向后寻找第一个匹配的 j 的字符
        for (; i < s.length(); ++i) {
          if (p.charAt(j) == '?' || s.charAt(i) == p.charAt(j)) {
            if (isMatch(s, i + 1, p, j + 1)) {
              return true;
            }
          }
        }
        return false;
      } else if (pCh == '?' || pCh == s.charAt(i)) {
        return isMatch(s, i + 1, p, j + 1);
      }

      return false;
    }
  }

}
